/**
 * 108. 将有序数组转换为二叉搜索树
 *
 * 【简单】
 *
 * 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。
 *
 * 示例 1：
 * 【https://assets.leetcode.com/uploads/2021/02/18/btree1.jpg】
 * 输入：nums = [-10,-3,0,5,9]
 * 输出：[0,-3,9,-10,null,5]
 * 解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
 * 【https://assets.leetcode.com/uploads/2021/02/18/btree2.jpg】
 *
 * 示例 2：
 * 【https://assets.leetcode.com/uploads/2021/02/18/btree.jpg】
 * 输入：nums = [1,3]
 * 输出：[3,1]
 * 解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
 */

import { TreeNode } from '../utils/tree'

//递归
// 二叉搜索树的中序遍历是升序的，本题中给出的数组刚好是升序的，相当于通过中序遍历恢复二叉搜索树
// 可以选择升序序列中的任意位置的元素作为根节点，该元素左边的升序序列构建左子树，右边的升序序列构建右子树
// 题目又要求高度平衡，所以我们需要选择升序序列的中间位置的元素作为根节点即可

function sortedArrayToBST(nums: number[]): TreeNode | null {
	if (nums.length === 0) {
		return null
	}
	const buildTree = (nums, left, right) => {
		if (left > right) {
			return null
		}

		const mid = Math.floor(left + (right - left) / 2)
		const root = new TreeNode(nums[mid])
		root.left = buildTree(nums, left, mid - 1)
		root.right = buildTree(nums, mid + 1, right)

		return root
	}

	return buildTree(nums, 0, nums.length - 1)
}
